package leetcode.f1t100;

import java.util.ArrayList;
import java.util.List;

/**
 * 给一串纯数字字符串, 返回加上3个点可能的IP值
 * https://leetcode.com/problems/restore-ip-addresses/
 *
 * @author lichx
 * @createTime 2024/2/18 11:18
 */
public class Q93_RestoreIpAddresses {

    public static void main(String[] args) {
        Q93_RestoreIpAddresses bean = new Q93_RestoreIpAddresses();
        List<String> stringList = bean.restoreIpAddresses("10111");
        System.out.println(stringList);
    }

    public List<String> restoreIpAddresses(String s) {
        char[] chars = s.toCharArray();
        return restoreIpAddresses(chars, 0, new ArrayList<>());
    }

    private List<String> restoreIpAddresses(char[] chars, int index, List<Integer> temp) {

        List<String> ans = new ArrayList<>();
        if (index == chars.length) {
            if (temp.size() == 4) {
                StringBuilder sb = new StringBuilder();
                for (Integer num : temp) {
                    sb.append(num).append(".");
                }
                sb.deleteCharAt(sb.length() - 1);
                ans.add(sb.toString());
                return ans;
            }
            return ans;
        }

        temp.add(chars[index] - '0');
        ans.addAll(restoreIpAddresses(chars, index + 1, temp));
        temp.remove(temp.size() - 1);

        if (chars[index] != '0' && index + 2 <= chars.length) {
            temp.add((chars[index] - '0') * 10 + (chars[index + 1] - '0'));
            ans.addAll(restoreIpAddresses(chars, index + 2, temp));
            temp.remove(temp.size() - 1);
        }

        if (chars[index] != '0' && index + 3 <= chars.length) {
            int num = (chars[index] - '0') * 100 + (chars[index + 1] - '0') * 10 + (chars[index + 2] - '0');
            if (num <= 255) {
                temp.add(num);
                ans.addAll(restoreIpAddresses(chars, index + 3, temp));
                temp.remove(temp.size() - 1);
            }
        }

        return ans;
    }
}
